home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 501-525 / disk_519 / oaklisp / src.lzh / stacks.h < prev    next >
C/C++ Source or Header  |  1991-06-15  |  8KB  |  321 lines
  1. /* Copyright (C) 1987, Barak Pearlmutter & Kevin Lang. */
  2.  
  3.  
  4. /* STACK_BUFFER_SIZE is how big the active part of the stack is, while
  5.    STACK_BUFFER_HYSTERESIS is how much of the buffer is not flushed to
  6.    the heap when an overflow occurs.  MAX_SEGMENT_SIZE is the maximum
  7.    amount of data put into a single stack segment when flushing the buffer.
  8.  
  9.    The tradeoffs are as follows:
  10.  
  11.    Making STACK_BUFFER_SIZE bigger increases performance by making overflows
  12.    less frequent.  Although it makes continuation creation more expensive
  13.    each time, the amortized cost remains the same or decreases.
  14.  
  15.    Making STACK_BUFFER_HYSTERESIS bigger should decrease underflow
  16.    frequency, but make call/cc more expensive.  It should also makes
  17.    pushing like mad forever more expensive, since the data in the
  18.    hysteretic section has to be copied twice, once from top to bottom and
  19.    once out into the heap.
  20.  
  21.    Making MAX_SEGMENT_SIZE bigger makes continuations somewhat more costly.
  22.    Making it smaller makes the header overhead of each segment
  23.    a greater fraction of the cost.
  24.  
  25.    For portability, STACK_BUFFER_SIZE had better be an int! */
  26.  
  27. #ifdef BIGINT
  28. #define STACK_BUFFER_SIZE 32768L
  29. #else
  30. #define STACK_BUFFER_SIZE 8192L
  31. #endif
  32.  
  33. #define STACK_BUFFER_HYSTERESIS 32
  34.  
  35. #define MAX_SEGMENT_SIZE 64
  36.  
  37.  
  38. /*
  39.   #define val_stk_ptr val_stk.ptr
  40.   #define UNOPTV(x)
  41.   #define cxt_stk_ptr cxt_stk.ptr
  42.   #define UNOPTC(x)
  43.   */
  44.  
  45. #define UNOPTV(x) x
  46. #define UNOPTC(x) x
  47.  
  48.  
  49.  
  50.  
  51. #define CONTEXT_FRAME_SIZE 3    /* This is not a tunable parameter. */
  52.  
  53.  
  54.  
  55.  
  56. #define SAVE_PTRS()            \
  57. {                    \
  58.   UNOPTV(val_stk.ptr = val_stk_ptr);    \
  59.   UNOPTC(cxt_stk.ptr = cxt_stk_ptr);    \
  60. }
  61.  
  62. #define RETR_PTRS()            \
  63. {                    \
  64.   UNOPTC(cxt_stk_ptr = cxt_stk.ptr);    \
  65.   UNOPTV(val_stk_ptr = val_stk.ptr);    \
  66. }
  67.  
  68. typedef struct
  69. {
  70.   ref type_field;
  71.   ref length_field;
  72.   ref previous_segment;
  73.   ref data[1];            /* I want 0 here, but C gets mad. */
  74. } segment;
  75.  
  76. #define SEGMENT_HEADER_LENGTH    (sizeof(segment)/sizeof(ref)-1L)
  77.  
  78.  
  79. typedef struct
  80. {
  81.   ref segment;            /* The segment to pop from. */
  82. #ifdef MALLOC_STACK_BUFFER
  83.   ref *data;            /* The buffer itself. */
  84. #else
  85.   ref data[STACK_BUFFER_SIZE];    /* The buffer itself. */
  86. #endif
  87.   ref *ptr;            /* This is updated when calling out.  It points
  88.                    to the top value. */
  89.   int pushed_count;        /* Number of references heaped. */
  90. } stack;
  91.  
  92.  
  93.  
  94.  
  95. #define FLUSHVAL(amount_to_leave)        \
  96. {                        \
  97.   SAVE_PTRS();                    \
  98.   flush_buffer(&val_stk, (amount_to_leave));    \
  99.   RETR_PTRS();                    \
  100. }
  101.  
  102. #define FLUSHCXT(amount_to_leave)        \
  103. {                        \
  104.   SAVE_PTRS();                    \
  105.   flush_buffer(&cxt_stk, (amount_to_leave));    \
  106.   RETR_PTRS();                    \
  107. }
  108.  
  109. #define UNFLUSHVAL(n)            \
  110. {                    \
  111.   UNOPTV(val_stk.ptr = val_stk_ptr);    \
  112.   unflush_buffer(&val_stk, (n));    \
  113.   UNOPTV(val_stk_ptr = val_stk.ptr);    \
  114. }
  115.  
  116. #define UNFLUSHCXT(n)            \
  117. {                    \
  118.   UNOPTC(cxt_stk.ptr = cxt_stk_ptr);    \
  119.   unflush_buffer(&cxt_stk, (n));    \
  120.   UNOPTC(cxt_stk_ptr = cxt_stk.ptr);    \
  121. }
  122.  
  123.  
  124.  
  125. /* Use this for looking at the top of stack at any time.  Use as lvalue too. */
  126. #define PEEKVAL()    (*val_stk_ptr)
  127.  
  128. /* Use this for looking before the top of stack, only when you're sure the
  129.    buffer has enough stuff in it. */
  130. #define PEEKVAL_UP(x)    (*(val_stk_ptr-(x)))
  131.  
  132. #define PUSHVAL(r)                        \
  133. {                                \
  134.   if (val_stk_ptr == &val_stk.data[STACK_BUFFER_SIZE-1])    \
  135.     {                                \
  136.       GC_MEMORY(r);                        \
  137.       SAVE_PTRS();                        \
  138.       flush_buffer(&val_stk, 0);                \
  139.       RETR_PTRS();                        \
  140.       GC_RECALL(*++val_stk_ptr);                \
  141.     }                                \
  142.   else                                \
  143.     *++val_stk_ptr = (r);                    \
  144. }
  145.  
  146.  
  147. /* Use this if you're SURE that an overflow is impossible. */
  148. #define PUSHVAL_NOCHECK(r)    { *++val_stk_ptr = (r); }
  149.  
  150.  
  151. #define POPVAL(v)        \
  152. {                \
  153.   CHECKVAL_POP(1);        \
  154.   (v) = *val_stk_ptr--;        \
  155. }
  156.  
  157.  
  158. #define PUSHVAL_IMM(r)    \
  159. {            \
  160.   CHECKVAL_PUSH(1);    \
  161.   PUSHVAL_NOCHECK((r));    \
  162. }
  163.  
  164. /* Preserve b in the event of GC. */
  165. #define PUSHVAL_PRESERVE1(r,b)                    \
  166. {                                \
  167.   if (val_stk_ptr == &val_stk.data[STACK_BUFFER_SIZE-1])    \
  168.     {                                \
  169.       GC_MEMORY(b);                        \
  170.       GC_MEMORY(r);                        \
  171.       SAVE_PTRS();                        \
  172.       flush_buffer(&val_stk, 0);                \
  173.       RETR_PTRS();                        \
  174.       GC_RECALL(*++val_stk_ptr);                \
  175.       GC_RECALL(b);                        \
  176.     }                                \
  177.   else                                \
  178.     *++val_stk_ptr = (r);                    \
  179. }
  180.  
  181. /* This pops and return the top of the value stack, without checking for
  182.    underflow.  Use it if you're SURE that underflow is not possible. */
  183. #define POPVAL_NOCHECK()    (*val_stk_ptr--)
  184.  
  185.  
  186. /* This ensures that n guys can be popped without underflow. */
  187. #define CHECKVAL_POP(n)                \
  188. {                        \
  189.   if (val_stk_ptr <= &val_stk.data[(n)-1])    \
  190.     UNFLUSHVAL((n));                \
  191. }
  192.  
  193. /* This ensures that n guys can be popped without underflow. */
  194. #define CHECKCXT_POP(n)                \
  195. {                        \
  196.   if (cxt_stk_ptr <= &cxt_stk.data[(n)-1])    \
  197.     UNFLUSHCXT((n));                \
  198. }
  199.  
  200. /* This ensures that n guys can be pushed without overflow. */
  201. #define CHECKVAL_PUSH(n)                    \
  202. {                                \
  203.   if (val_stk_ptr >= &val_stk.data[STACK_BUFFER_SIZE-(n)])    \
  204.     FLUSHVAL(STACK_BUFFER_HYSTERESIS);                \
  205. }
  206.  
  207. /* This ensures that n guys can be pushed without overflow. */
  208. #define CHECKCXT_PUSH(n)                    \
  209. {                                \
  210.   if (cxt_stk_ptr >= &cxt_stk.data[STACK_BUFFER_SIZE-(n)])    \
  211.     FLUSHCXT(STACK_BUFFER_HYSTERESIS);                \
  212. }
  213.  
  214.  
  215. /* This routine avoids having a bogus reference in the segments. */
  216. #define BASH_SEGMENT_TYPE(x) { cxt_stk.segment = val_stk.segment = e_nil; }
  217.   
  218.  
  219.  
  220. extern void init_stk(), flush_buffer(), unflush_buffer();
  221.  
  222.  
  223.  
  224. /* This, which pops some guys off the value stack, is inefficient because
  225.    it copies guys into the buffer and then pops them off.  A better
  226.    thing should be written.  */
  227. #define POPVALS(x)    \
  228. {            \
  229.   CHECKVAL_POP((x));    \
  230.   val_stk_ptr -= (x);    \
  231. }
  232.  
  233. #define POPCXTS(x)    \
  234. {            \
  235.   CHECKCXT_POP((x));    \
  236.   cxt_stk_ptr -= (x);    \
  237. }
  238.  
  239.  
  240. #define PUSH_CONTEXT(offset)                    \
  241. {                                \
  242.   CHECKCXT_PUSH(CONTEXT_FRAME_SIZE);                \
  243.   *++cxt_stk_ptr =                        \
  244.        INT_TO_REF((long)e_pc - (long)e_code_segment        \
  245.               + 2*(offset));                \
  246.   *++cxt_stk_ptr = e_current_method;                \
  247.   *++cxt_stk_ptr = PTR_TO_LOC(e_bp);                \
  248. }
  249.  
  250.  
  251. #define POP_CONTEXT()                    \
  252. {                            \
  253.   CHECKCXT_POP(CONTEXT_FRAME_SIZE);            \
  254.   e_bp = LOC_TO_PTR(*cxt_stk_ptr--);            \
  255.   e_current_method = *cxt_stk_ptr--;            \
  256.   e_env = REF_TO_PTR(e_current_method);            \
  257.   e_code_segment = SLOT(e_env,METHOD_CODE_OFF);        \
  258.   e_env = REF_TO_PTR(SLOT(e_env,METHOD_ENV_OFF));    \
  259.   e_pc = (unsigned short *)                \
  260.     ((long)e_code_segment                \
  261.      + REF_TO_INT(*cxt_stk_ptr--));            \
  262. }
  263.  
  264.  
  265. /* No preparation needed! */
  266. #define gc_prepare(pstk)
  267.  
  268.  
  269. #define bash_val_height(h)        \
  270. {                    \
  271.   int to_pop = val_height()-(h);    \
  272.                     \
  273.   POPVALS(to_pop);            \
  274. }
  275.  
  276.  
  277. #define bash_cxt_height(h)        \
  278. {                    \
  279.   int to_pop = cxt_height()-(h);    \
  280.                     \
  281.   POPCXTS(to_pop);            \
  282. }
  283.  
  284.  
  285.  
  286. #define MAKE_BACK_VAL_PTR(v,dist)    \
  287. {                    \
  288.   CHECKVAL_POP((dist));            \
  289.   (v) = val_stk_ptr - (dist);        \
  290. }
  291.  
  292.  
  293. #define stk_height(stk) ((stk).ptr - (&(stk).data[0]-1) + (stk).pushed_count)
  294. #define val_height() (val_stk_ptr - (&val_stk.data[0]-1) + val_stk.pushed_count)
  295. #define cxt_height() (cxt_stk_ptr - (&cxt_stk.data[0]-1) + cxt_stk.pushed_count)
  296.  
  297. extern void dump_stack_proc();
  298.  
  299.  
  300. #define dump_val_stk()            \
  301. {                    \
  302.   UNOPTV(val_stk.ptr = val_stk_ptr);    \
  303.   dump_stack_proc(&val_stk);        \
  304. }
  305.  
  306.  
  307. #define dump_cxt_stk()            \
  308. {                    \
  309.   UNOPTC(cxt_stk.ptr = cxt_stk_ptr);    \
  310.   dump_stack_proc(&cxt_stk);        \
  311. }
  312.  
  313. #ifdef PROTOTYPES
  314.  
  315. extern void        flush_buffer(stack *pstk, int amount_to_leave);        
  316. extern void        unflush_buffer(stack *pstk, int n);        
  317. extern void        dump_stack_proc(stack *pstk);        
  318. extern void        init_stk(stack *pstk);        
  319.  
  320. #endif
  321.